\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 2}

\paragraph{Задача 1.} Вещественная матрица называется бистохастической, если всее ее элементы неотрицательны, и сумма элементов в каждой строке и в каждом столбце равна 1.
\begin{enumerate}
\item Докажите, что в бистохастической матрице можно найти $n$ (строго) положительных элементов, никакие два из которых не стоят в одной строке или в одном столбце.

\item Докажите, что бистохастическая матрица является выпуклой комбинацией матриц перестановок. (Матрица перестановок - матрица, у которой в каждой строке и каждом столбце стоит одна единица и $n-1$ нуль. Выпуклая комбинация - линейная комбинация с неотрицательными коэффициентами, дающими в сумме 1.)
\end{enumerate}

\begin{Proof}
\begin{enumerate}
\item Сопоставим матрице двудольный граф $G$, пусть вершины его первой доли обозначают строки матрицы, а вершины второй доли стобцы. Ребро графа обозначается, что на пересечении соответствующих столбца и строки стоит не ноль. В таком графе из каждой вершины первой доли и из каждой вершины второй есть как минимум одно ребро, и количество вершин в долях совпадает. Далее покажем, что для любое $k$-подмножество множества вершин первой доли соединено, не менее чем с $k$-вершинами из второй доли. Для этого предположим обратное, тогда получается, что можно перестановкой строк и столбцов получить в исходной матрице прямоугольную подматрицу размера $k \times l$, где $l < k$, в этой подматрице сумма элементов любой строки равна 1, а сумма элементо каждого столбца $\le 1$, но такого быть не может, следовательно протиоречие. Следовательно в графе можно соединить попарно вершины всех долей, и множество таких ребер соответствует множеству строго положительных элементов исходной матрицы, причем никакая пара из них не лежит в одной строке или столбце.
\end{enumerate}
\end{Proof}

\paragraph{Задача 2.} Есть n юношей и n девушек. Каждый юноша знает хотя бы одну девушку. Докажите, что можно некоторых юношей поженить на знакомых девушках так, чтобы женатые юноши не знали незамужних девушек.

\begin{Proof}
Во-первых, скажем, что в каждый юноша знаком с более чем одной девушкой, в противном случае, поженив юношу на единственной знакомой девушке, мы доказываем условие теоремы, т. е. проблемы возникают только в случае, если юноша знаком более чем с одной девушкой.

Далее рассматриваем 2 юношей, в совокупности они знакомы с 2 и более девушками, добавим к ним еще одного юношу, если втроем они знакомы менее чем с тремя девушками, то всех знакомых девушек можно поженить на парянх и у парней не останется незнакомых неженатых девушек, если они знакомы с тремя и более девушками, то добавим к ним еще одного парня и вновь сравним количество девушек и парней, если парней меньше или столько же, то добавим к ним еще одного и так далее.

Такой процесс не может продолжаться до бесконечности, так как число девушек и юношей конечно, и в конце концов, мы либо придем к неинтересному случаю, когда $k$ парней знакомы с $l$ девушками и $k>l$, либо покроем все множество парней и девушек, а по лемме о девушках (свадьбах) в этом случае их всех можно поженить попарно.
\end{Proof}

\paragraph{Задача 3.} Даны $k$ мальчиков и $2k-1$ конфет. Докажите, что можно дать каждому мальчику по конфете так, чтобы мальчику, которому не нравится его конфета, не нравились и конфеты отсальных мальчиков.
\begin{Proof}
Пусть в двудольном графе, если конфета нравится мальчику, то они соединены ребром. Выбираем произвольного мальчика, если ему не нравится ни одна конфета, то даем ему любую и удаляем его и конфету из графа, если же ему нравится одна или более конфет, то выбираем еще одного мальчика и рассматриваем их вместе. Если на $i$-ом этапе рассмотрения имеется имеется $n$ мальчиков и $m$ конфет, которые в совокупности им нравятся, если $n>m$ то дадим всем этим мальчикам по одной конфете, которая им не нравится, и удалим из графа этих мальчиков, отданные им конфеты и все конфеты, которые им нравятся (таких не более $2n-1$), в случае, если $n \le m$ добавим в рассмотрение еще одного мальчика.

Таким образом, мы либо выбросим всех $k$ мальчиков и не более $2k-1$ конфеты из графа, либо останется $n$ мальчиков, которым в совокупноти нравится $m>n$ конфет, и любому их $l\le n$ подмножеству нравится не менее $l$ конфет, значит можно раздать каждому из них по конфете, которая ему нравится. 
\end{Proof}

\paragraph{Задача 4.} На улице Болтунов живут $n$ юношей и $n$ девушек, причем каждый юноша знаком ровно с $k$ девушками, а каждая деушка ровно с $k$ юношами.
\begin{enumerate}
\item Докажите, что все юноши и девушки могут одноременно говорить со своими знакомыми по телефону.

\item Докажите, что юноши и девушки могут звонить друг другу по телефону так, чтобы за $k$ часо каждый поговорил с каждым из своих знакомых по часу.
\end{enumerate}

\begin{Proof}
\begin{enumerate}
\item Любые $l>k$ юношей знакомы в совокупности с $l$ и более девушками. Докажем это от противного. Пусть это не так, т. е. сущестует подмножесто из $l$ юношей такое, что они знакомы с $m$ девушками, причем $m<l$. Каждое такое знакомство соответствует ребру в двудольном графе, но тогда получается, что $l$ юношей соединины $l \cdot k$ ребрами с $m$ девушками, которые в свою очередь соединены не более чем $m \cdot k$ ребрами с юношами, но это не возможно т. к. $l \cdot k > m \cdot k$, следовательно получили противоречие, а значит можно применить лемму о деушках.

\item В предыдущем пункте доказано, что если каждый юноша знаком ровно с $k$ девушками и каждая девушка знакома ровно с $k$ юношами, то они могут одновременно разговаривать по телефону со своими знакомыми, но на $k$ не было никаких ограничений (кроме того, что $k \ge 0$). Поступим следующием образом, после каждого телефонного разговора ввыкинем из двудольного графа знакомств ребро между говорившими людьми, тогда получим граф, в котором степень каждой вершины равна $k-1$, а это опять в точности условие предыдущего пункта задачи, следовательно опять каждый юноша и каждая девушка могут одновременно поговорить с одним из $k-1$ отсавшихся знакомых.
\end{enumerate}
\end{Proof}

\paragraph{Задача 7.} (Обобщенная лемма о девушках) В некоторой компании любые $k$ юношей знают хотя бы $k-m$ девушек $k=m,m+1,...$. Докажите, что можно поженить всех юношей, кроме m, на знакомых девушках.

\begin{Proof}
Добавим в компанию $m$ виртуальных девушек и познакомим каждого парня с каждой девушкой. Тогда в новом графе знакомств выполняется условие леммы Холла (так как теперь каждые $k$ парней знакомы с $k-m+m$ девушками как минимум). Построим паросочетние между юношами и всеми девушками, тех юношей, которые в паросочетании соединены с иртуальными девушками не больше $m$, следовательно в исходном графе знакомств можно было соединить в паросочетание как минимум $n-m$ юношей, где $n$-число всех юношей.
\end{Proof}

\paragraph{Задача 9.}
\begin{itemize}
\item Дано семейство множеств. Объединение любых $k$ ($k=1,2,...$) множест из этого семейства содержит не менее $k$ элементов. Докажите, что можно  каждом множестве выделить элемент ("представителя") так, чтобы все представители были различны.

\item Дано векторное пространство $X$ и семейство его подмножеств. Известно, что для любых $k$ ($k=1,2,...$) множеств из этого семейства их объединение содержит $k$ линейно независимых векторов. Докажите, что можно в каждом множестве выбрать по вектору так, чтобы выбранные векторы (а по-моему, правильно писать вектора) были линейно независимы.
\end{itemize}

\begin{Proof}
\begin{itemize}
\item Сопоставляем каждому множеству вершину в первой доле графа, а каждому элементу множества вершину во второй доле графа. Получаем двудольный граф, в котором вершина-множество соединено с вершиной-элементом, в том случае, если элемент принадлежит множеству. В этом графе по лемме Холла, можно сопоставить каждой вершине-множеству сопоставить вершину-элемент, так чтобы связывающие их ребра не пересекались. (Теорема о независимых представителях, просто другая формулировка леммы Холла)

\item Возмем множество $M1$ из семейства $X$, все вектора в нем линейно зависимы (по услоию, что объединение любых $k$ множеств содержит $k$ линейно независимых векторов, в случае если $k=1$ получаем исходное положение) и это справедливо для любого множества из семейства. Теперь выберем другое множество $M2$, в нем так же как и в первом множестве все вектора линейно зависимы, но $M1 \cup M2$ содержит уже 2 линено независиых вектора, т. е. ни один вектор из $M1$ не является линеной комбинацией векторов из $M2$, так как множества выбирались произвольно, то это справедливо для любой пары множеств. Таким образом выбрав по одному любому вектору из каждого множества семейства получаем набор из $n$ линейно независимых векторов.
\end{itemize}
\end{Proof}

\end{document}
